#include <bits/stdc++.h>
using namespace std;

/*
417. 太平洋大西洋水流问题
已解答
中等
相关标签
premium lock icon
相关企业
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。

这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。

岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。

返回网格坐标 result 的 2D 列表 ，其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。

 

示例 1：



输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
示例 2：

输入: heights = [[2,1],[1,2]]
输出: [[0,0],[0,1],[1,0],[1,1]]
 

提示：

m == heights.length
n == heights[r].length
1 <= m, n <= 200
0 <= heights[r][c] <= 105
*/

// 法一
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        // bfs dfs 都可以   
        // 双向BFS
        if (heights.empty()) return {};
        
        int m = heights.size();
        int n = heights[0].size();
        // 标记能流向太平洋和大西洋的单元格
        vector<vector<bool>> pacific(m, vector<bool>(n, false));
        vector<vector<bool>> atlantic(m, vector<bool>(n, false));
        
        // 四个方向偏移量（上、下、左、右）
        vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        // BFS队列：分别处理太平洋和大西洋
        queue<pair<int, int>> qPac, qAtl;
        
        // 初始化太平洋边界：第一行和第一列的单元格可直接流入太平洋
        for (int i = 0; i < m; ++i) {
            qPac.emplace(i, 0);
            pacific[i][0] = true;
        }
        for (int j = 0; j < n; ++j) {
            qPac.emplace(0, j);
            pacific[0][j] = true;
        }
        
        // 初始化大西洋边界：最后一行和最后一列的单元格可直接流入大西洋
        for (int i = 0; i < m; ++i) {
            qAtl.emplace(i, n - 1);
            atlantic[i][n - 1] = true;
        }
        for (int j = 0; j < n; ++j) {
            qAtl.emplace(m - 1, j);
            atlantic[m - 1][j] = true;
        }
        
        // BFS标记所有能流向太平洋的单元格
        bfs(heights, qPac, pacific, dirs);
        // BFS标记所有能流向大西洋的单元格
        bfs(heights, qAtl, atlantic, dirs);
        
        // 收集既能流向太平洋又能流向大西洋的单元格
        vector<vector<int>> result;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (pacific[i][j] && atlantic[i][j]) {
                    result.push_back({i, j});
                }
            }
        }
        
        return result;
    }

    // helper
    // 从边界单元格出发，标记所有可流入对应海洋的单元格
    void bfs(const vector<vector<int>>& heights, queue<pair<int, int>>& q, 
             vector<vector<bool>>& visited, const vector<pair<int, int>>& dirs) {
        int m = heights.size();
        int n = heights[0].size();
        
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            
            // 检查四个方向的相邻单元格
            for (const auto& [dx, dy] : dirs) {
                int nx = x + dx;
                int ny = y + dy;
                
                // 相邻单元格需在网格范围内，且未被标记，且高度 >= 当前单元格（水可从相邻单元格流向当前单元格）
                if (nx >= 0 && nx < m && ny >= 0 && ny < n 
                    && !visited[nx][ny] 
                    && heights[nx][ny] >= heights[x][y]) {
                    visited[nx][ny] = true;  // 标记为可流入该海洋
                    q.emplace(nx, ny);      // 加入队列继续扩散
                }
            }
        }
    }
};

// 法二  状态压缩
class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        vector<vector<int>> ans;
        int m = heights.size(), n = heights[0].size();
        const vector<vector<int>> dir = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // 四向偏移
        
        // 访问标记：用数值区分状态
        // 1: 能流向太平洋；10: 能流向大西洋；11: 两者都能（1+10）
        vector<vector<int>> visited(m, vector<int>(n, 0));
        
        // 递归DFS：从边界反向搜索可流入对应海洋的单元格
        auto dfs = [&](auto&& dfs, int i, int j, bool isPacific) -> void {
            // 标记当前单元格：太平洋+1，大西洋+10
            visited[i][j] += isPacific ? 1 : 10;
            
            // 遍历四向邻居
            for (int k = 0; k < 4; ++k) {
                int x = i + dir[k][0];
                int y = j + dir[k][1];
                
                // 邻居需在网格内，且高度 >= 当前单元格（水可从邻居流向当前，进而入海）
                if (x < 0 || x >= m || y < 0 || y >= n || heights[x][y] < heights[i][j]) {
                    continue;
                }
                
                // 避免重复访问：太平洋未标记过 或 大西洋未标记过
                if (isPacific && visited[x][y] <= 0) { // 太平洋：未被标记（<=0）
                    dfs(dfs, x, y, isPacific);
                }
                if (!isPacific && visited[x][y] < 10) { // 大西洋：未被标记（<10）
                    dfs(dfs, x, y, isPacific);
                }
            }
        };
        
        // 初始化太平洋边界：上边界（i=0）和左边界（j=0）
        for (int i = 0; i < n; ++i) {
            if (visited[0][i] == 0) { // 未被太平洋标记过
                dfs(dfs, 0, i, true);
            }
        }
        for (int i = 0; i < m; ++i) {
            if (visited[i][0] == 0) { // 未被太平洋标记过
                dfs(dfs, i, 0, true);
            }
        }
        
        // 初始化大西洋边界：下边界（i=m-1）和右边界（j=n-1）
        for (int i = 0; i < n; ++i) {
            if (visited[m - 1][i] < 10) { // 未被大西洋标记过
                dfs(dfs, m - 1, i, false);
            }
        }
        for (int i = 0; i < m; ++i) {
            if (visited[i][n - 1] < 10) { // 未被大西洋标记过
                dfs(dfs, i, n - 1, false);
            }
        }
        
        // 收集同时能流向两个海洋的单元格（标记为11）
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (visited[i][j] == 11) {
                    ans.push_back({i, j});
                }
            }
        }
        
        return ans;
    }
};

// 规整点的写法
constexpr int DIRE[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 四向移动偏移量（下、右、上、左）

class Solution {
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        int m = heights.size(), n = heights[0].size();
        // 状态标记数组：1表示能流向太平洋，2表示能流向大西洋，3表示两者都能（1+2）
        vector<vector<int>> graph(m, vector<int>(n, 0));
        
        // 标记太平洋可达区域：左边界（i,0）和上边界（0,j）
        for (int i = 0; i < m; ++i) bfs(heights, graph, m, n, i, 0, 1);
        for (int j = 0; j < n; ++j) bfs(heights, graph, m, n, 0, j, 1);
        
        // 标记大西洋可达区域：右边界（i,n-1）和下边界（m-1,j）
        for (int i = 0; i < m; ++i) bfs(heights, graph, m, n, i, n-1, 2);
        for (int j = 0; j < n; ++j) bfs(heights, graph, m, n, m-1, j, 2);
        
        // 收集同时可达两个海洋的单元格（状态为3）
        vector<vector<int>> ans;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (graph[i][j] == 3)
                    ans.push_back({i, j});
        
        return ans;
    }
    
    // 从(i,j)开始扩散标记：f=1标记太平洋可达，f=2标记大西洋可达
    void bfs(vector<vector<int>>& heights, vector<vector<int>>& graph, int m, int n, int i, int j, int f) {
        // 越界 或 已被当前海洋标记过（避免重复处理），直接返回
        if (i < 0 || j < 0 || i == m || j == n || graph[i][j] >= f) return;
        
        graph[i][j] += f; // 标记当前单元格为可达当前海洋
        
        // 遍历四向邻居，仅当邻居高度>=当前高度（水可从邻居流向当前，进而入海）时继续扩散
        for (auto& dire : DIRE) {
            int x = i + dire[0];
            int y = j + dire[1];
            if (x < 0 || y < 0 || x == m || y == n) continue; // 邻居越界则跳过
            if (heights[x][y] >= heights[i][j]) {
                bfs(heights, graph, m, n, x, y, f);
            }
        }
    }
};